package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/ugly-number-ii/'>丑数 II(Ugly Number II)</a>
 * <p>给你一个整数 n ，请你找出并返回第 n 个 丑数 。</p>
 * <p>丑数 就是质因子只包含 2、3 和 5 的正整数。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：n = 10
 *      输出：12
 *      解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
 *
 * 示例 2：
 *      输入：n = 1
 *      输出：1
 *      解释：1 通常被视为丑数。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= n <= 1690</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/15 9:36
 */
public class LC0264UglyNumber_II_M {
    static class Solution {
        public int nthUglyNumber(int n) {
            int[] dp = new int[n + 1];
            dp[1] = 1;
            int p2 = 1;
            int p3 = 1;
            int p5 = 1;
            for (int i = 2; i <= n; i++) {
                // p2 控制 2的倍数
                int num2 = dp[p2] * 2;
                // p3 控制 3的倍数
                int num3 = dp[p3] * 3;
                // p5 控制 5的倍数
                int num5 = dp[p5] * 5;
                // 取三者的最小值，作为下一个丑数
                dp[i] = Math.min(Math.min(num2, num3), num5);
                // 将最小值扩大对应倍数
                if (dp[i] == num2) {
                    ++p2;
                }
                if (dp[i] == num3) {
                    ++p3;
                }
                if (dp[i] == num5) {
                    ++p5;
                }
            }
            return dp[n];
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.nthUglyNumber(1690));
    }
}
